Conquest AI Project

Version 1.1

Paul McCartney
paul@informatics.wustl.edu

Washington University Computer Science Department

Table of Contents

1 Introduction	1
2 Game Description and Rules	2
2.1  Select Country Round	2
2.2  Place Armies Round	3
2.3  Attack Round	3
2.3.1  Place Armies	3
2.3.2  Attack	3
2.3.3  Fortify	4
2.4  Armies Given per Turn	4
2.4.1  Countries	4
2.4.2  Cards	4
2.4.3  Continents	5
2.4.4  Total Armies per Turn	5
3 Software Organization	5
3.1  Players Source Code	6
3.2  Starting Conquest and Running a Game	6
4  Implementation of a Player	7
4.1  Copying the Player Template	7
4.2  Conquest Primitives	8
4.2.1  Continent Methods	8
4.2.2  Country Methods	9
4.2.3  Player Information Methods	10
4.2.4  Validation Methods	11
4.2.5  Miscellaneous Methods	11
4.3  User Defined Computer Player Methods	13
4.3.1  Select Country	13
4.3.2  Place Armies	13
4.3.3  Attack	14
4.3.4  Fortify	14
5 LISP/CLOS Programming Tips	15
6 Conquest Game Strategy Tips	16

1 Introduction

The purpose of this document is to introduce the Conquest AI project.  “Conquest” is an interactive strategy game played between two or more players (see section 2.0).  The software provided by this project includes the user interface (i.e. graphics screen, human interaction), program control, and a basic computer player.  The job of the users of this project is to design and implement computer players.  Implementation of computer players is done using the Macintosh Common LISP environment, using CLOS objects as a basis.  This document assumes that the reader is familiar with CLOS and the Macintosh Common LISP environment.

This version of Conquest is not “hard coded” for one particular board (e.g. planet Earth).  Testing and evaluation of computer players should involve multiple boards (e.g. Mars, Earth, etc.) to ensure that the computer players have a sufficiently general strategy (i.e. can they win on more than one board). 

This software was developed by me in Fall of 1992 while I was a teaching assistant for a graduate level AI course.  I made this software so that each student in the course could implement their own computer player.  At the end of the course, we had a Conquest tournament with all of the students’ players.  The player source code of the first and second place winners of the tournament are included with this software (Bob Kollmeyer, first place; Terry Idol, second place).

Conquest may be distributed free of charge to anyone.  I’d be interested to hear from the users of this software (via email), especially if challenging computer players are created.

2 Game Description and Rules

Figure 2-1:  Conquest running on planet Earth with five players.

Conquest is similar to the RISK board game.  For simplicity, Conquest varies a bit from RISK.

Conquest can be played by two or more players, up to the number of countries on the board.  Any combination of human and computer players may participate in a game.

The Conquest board consists of a collection of countries which are represented by the interface as squares.  Each country is adjacent to other countries.  This adjacency is represented by a line between pairs of countries (i.e. country i and country j are adjacent iff there is a line connecting them).  At a theoretical computer science level, the collection of countries form an undirected, connected, simple graph.

A continent is composed of a subset of the collection of countries.  Every country on the board is a member of some continent (there are typically multiple continents).

Each country may be owned by a player.  A country is owned by a player if that player has at least one army on the country.  The interface represents ownership of a country through color (i.e. if a player owns a country, the country is colored with that player's color).  The object of the game is for one player to own every country on the board.

2.1  Select Country Round

Initially, none of the board's countries are owned.  In the first round of the game players alternate turns, selecting one country to during own each turn (a human player does this by simply clicking on the country).  A selected country changes to the color of its owner.  This round is completed when all of the countries are owned by some player.

2.2  Place Armies Round

After the Select Country round, at the beginning of a player's turn, the player is given a number of armies.  A player places the armies on countries that he/she owns.  The interface shows (n-1) of the armies that a country has in a box on the country.  The game has a limit on the number of armies that a single country can hold.

This round consists of some number of alternating turns in which each player places his/her armies on countries that he/she owns (a human player does this by entering a number of armies into the edit text box and clicking on a country to place the armies on, or shift-clicking on a country to place all armies on that country).

2.3  Attack Round

From this point on, the game consists of a sequence of alternating turns between the players of the game.   A single turn will be defined as a sequence of three move types:  place armies, attack, fortify.  That is, the player first places all of his/her armies, then attacks some number of enemies, and then fortifies some number of times.

2.3.1  Place Armies 

A player is given armies which must be placed on countries that the player owns.  Note that all of the armies do not need to be placed on the same country (e.g. you could place a single army on each country that you own).  All armies must be placed before moving on.

2.3.2  Attack

A player's country may attack an adjacent country if the player's country has at least two armies (i.e. the country has a number on it) and the adjacent country is owned by some other player.  A human player first selects an attacker country by clicking on it (the country should turn into inverse video), and then selects an adjacent enemy country to attack by clicking on it.

The attack involves the armies on the two competing countries “fighting.”  The attacker attempts to defeat all of the armies on the defender's country and take it over.  The defender attempts to maintain ownership of its country.

Battles are performed between armies of the attacker and armies of  the defender.  A battle consists of generating a random number, n.  For a certain range of values of n, the attacker will win the battle.  When the attacker wins a battle, one of the armies is subtracted from the defender's armies.  Similarly, when the attacker does not win the battle, one of the armies is subtracted from the attacker's armies.  Currently, the odds are slightly in favor of the defender (the percentage chance of a defender losing a single battle is contained in the constant *dice-bias*,  which is currently 48).

Battles between the armies of the warring countries continue until one of the following conditions hold:
1)  The number of defender armies is zero.
2)  The number of attacker armies is one.
3)  The attacker has lost  m armies, where m is the attacker's loss threshold.

When an attacker defeats all of the armies on a defender's country, the attacker takes ownership of the defender's country.  One army is left on the attacker's country, and the remaining armies are moved to the newly conquered country.

Within the attack round, a player is free to attack as many different times as he/she is able.   The human player denotes the end of his/her attacks by pressing either the “done” or “fortify” button.  The “done” button advances to the next player's turn, while the "fortify" button changes to the fortify stage of the current player's turn.
 
2.3.3  Fortify

Fortify consists of moving some or all of a player’s armies on a country to adjacent countries that are owned by the player.  The player is permitted to do these moves any number of times for all the countries that he/she owns.  Note that the countries have a upper limit on the number of armies permitted on a single country.

The human player fortifies by clicking on the country to fortify from and placing the armies on adjacent countries (or back on the original country) as described in section 2.2.

2.4  Armies Given per Turn

The number of armies that a player is given per turn is determined by the following factors:
	1)  Countries owned
	2)  Continents owned
	3)  Conquest Cards

2.4.1  Countries

A player is given the following number of additional armies based on the number of countries owned. 

MAX (3, )

2.4.2  Cards

Whenever a player defeats at least one enemy within a turn (i.e. the player attacks an enemy country and takes over the country), the player is given a Conquest card.  At the beginning of a player's turn, if the player has a multiple of four number of cards then each set of four cards is "cashed in".

Cashing in a set of four cards gives the player additional armies.  The number of additional armies is called the Conquest value.  The Conquest value is initially five and increases by one each time a player turns in a set of cards until the Conquest value reaches its maximum of 50.

When a player totally defeats another player (i.e. a player attacks the last remaining country that another player owns and takes over that country), the attacking player is given the cards of the defeated player.

In the interface, the number of cards that each player owns is shown in the top left of the window in a box with the color of the player.

2.4.3  Continents

If a player owns all of the countries in a continent, the player is said to own the entire continent.  For every continent that a player owns at the beginning of his/her turn, the player is given the following number of additional armies:

Where Countries i is the number of countries in continent i.

2.4.4  Total Armies per Turn

MAX (3, ) +  + 

3 Software Organization

Figure 3-1:  Conquest AI Project Software Organization.

Figure 1 shows the software organization of the Conquest AI project.  Each circle in the diagram represents a CLOS object.  Given a game specification, a control object is created.  The control object, in turn, creates the window object (using the game specifications) and the player objects (using the class names supplied by the game specification).  Once everything is created, the control object plays the game with the given players until the game is finished (or the user aborts with Command-period).

3.1  Players Source Code

The source code for user defined players should be placed in the “PLAYERS” folder.  The system assumes that each user’s code is in its own folder and that a file called “@load.lisp” is contained in the folder to load all of the players files.

3.2  Starting Conquest and Running a Game

To start Conquest, load the file called “@start-conquest.lisp”.  

Once Conquest is loaded (files may be compiled the first time Conquest is loaded), a game can be run by calling the “play-conquest” function.  See example calls in “script.lisp.”

play-conquest
	Parameters:	&key	window-size		an MCL encoded point
				window-position	an MCL encoded point
				world			*earth-world*, *mars-world*, or *cs512-world*
				country-capacity	a positive integer
				players		a list of player specifications, the order of
							player specifications determines the turn order 
							in the game

	player specification 	=	(list <player-type> <player-name> <color>)

	player-type		=	A player CLOS object symbol name.
					Provided players include the following:
						1)  basic-player
						2)  human-player
						3)  tai2-player
						4)  rjk1-player
						5)  paul-player
						6)  paul-neutral-player
						
	player-name		=	a string

	color			=	an MCL encoded color

e.g.:

(in-package :conquest)

(play-conquest 
 :world *earth-world*
 :window-size #@(620 440)
 :players (list 
           (list 'human-player "Human" *white-color*)
           (list 'tai2-player "Terry" *green-color*)
           (list 'rjk1-player "Bob" *red-color*)
           (list 'basic-player "Franklin" *brown-color*)
           (list 'basic-player "Oldroyd" *yellow-color*)
           (list 'paul-player "Paul" *blue-color*)
           (list 'paul-neutral-player "Paul2" *orange-color*)
           ))

4  Implementation of a Player

Implementing a computer player involves creating a class which inherits from the class basic-player and implementing class methods called select-country, place-armies, attack, and fortify.  The control object communicates with each computer player through these methods.  That is, when the control object wants a computer player to make a move, it calls the appropriate method for the player.  That computer player's method is responsible for deciding what move to make.  To help in the decision, the basic-player class includes a number of "Conquest primitives".  The primitives are methods that return information about the state of the game (e.g. Who owns country x?  How many armies are on country y?).

By inheriting from the class basic-player, a computer player is given access to the basic player methods and object variables.  If any of the methods select-country, place-armies, attack, and fortify are not implemented in the inherited class, the basic player methods will be used.  The following object variables are accessible through any class that inherits from basic-player:

1)  ID:  This is a symbol representing the player-id (i.e. unique identifier) of the current player object.

2)  armies-to-lose:  This should be set to some integer value.  Control looks at the value of this variable to determine how many armies you are willing to use in a battle if you are attacking (i.e. your loss threshold; an attack will stop if  you lose at least that amount of armies).

See section 5.0 for examples of how to use object variables.

4.1  Copying the Player Template

A template for creating a player is provided.  This template is composed of a folder containing template files for each of the Conquest methods.  Each template file contains comments describing how to implement each part of the player as well as package information (each user works in a separate package to eliminate the possibility of identifier conflicts.

First, think of a unique identifier call your player (e.g. your first name or user ID, mine is named “paul”).

Create a copy of the folder named “generic-player” and place the copy into the “PLAYERS” folder.

Rename the copy of the generic player folder to contain your unique identifier (e.g. “paul-player”).

In each file of your copy, replace every occurrence of “generic” to your unique identifier (use the “Find/Replace” dialog, it’s faster).

The next time that you start Conquest, your player template will be loaded.  An entry in the “Docs” menu will be created for easy access of player files.  Also, a package with the name of your unique identifier will be created.  For convenience, when working on your player be sure to set the package in the Listener (e.g. (in-package :paul) ).

4.2  Conquest Primitives

The Conquest primitives return information about the current Conquest game.  Data returned include the following:

1)  Country:  A unique positive integer.

2)  Continent:  A unique symbol.

3)  Player:  A unique symbol.  I shall also refer to this as the player-id, to distinguish it from the player object.

4)  A list containing countries, continents, or player-ids.

4.2.1  Continent Methods

available-continents
	Parameters:	player		player object
			
	Returns:	A list of continents which have at least one available country.

conquest-continents
	Parameters:	player		player object
			
	Returns:	A list of all of the continents of the current Conquest board.

continent-countries-list
	Parameters:	player		player object
			continent	a continent

	Returns:	A list of all countries within continent.

continent-borders
	Parameters:	player		player object
			continent	a continent

	Returns:	A list of countries within continent which have at least one adjacent
			country that is not in the same continent.

4.2.2  Country Methods

available-countries
	Parameters:	player		player object
			continents	list of continents
					(optional; defaults to all of the continents)

	Returns:	A list of countries that are not owned by any player on one of the continents.

adjacent-countries
	Parameters:	player		player object
			country	a country

	Returns:	A list of countries that are adjacent to country.

adjacent-enemies
	Parameters:	player		player object
			country	a country 
			owner-id	player ID of a player
					(optional; defaults to the current owner country)

	Returns:	A list of countries adjacent to country which are owned by some 
			player and have owners that are not owner-id.

adjacent-allies
	Parameters:	player		player object
			country	a country 
			owner-id	player ID of a player
					(optional; defaults to the current owner country)

	Returns:	A list of countries adjacent to country which have owners that are
			owner-id.

armies-on-country
	Parameters:	player		player object
			country	a country

	Returns:	An integer representing the number of armies on country
			or nil if not owned.

country-owner
	Parameters:	player		player object
			country	a country

	Returns:	Player ID of the owner of country  or nil if country is not owned.

continent-of-country
	Parameters:	player		player object
			country	a country

	Returns:	Continent that the country is a member of.

border-p
	Parameters:	player		player object
			country	a country

	Returns:	T, if at least one adjacent country to country has a different owner.
			nil, otherwise.

interior-p
	Parameters:	player		player object
			country	a country

	Returns:	T, if no adjacent country to country is owned by a different owner.
			nil, otherwise.

4.2.3  Player Information Methods

conquest-players
	Parameters:	player		player object

	Returns:	A list of the player IDs of the players in the current game.

player-continents
	Parameters:	player		player object
			player-id	player ID of a player
					(optional; defaults to the ID of player)

	Returns:	A list of continent  IDs in which player-id owns every country 
			in the continent.

player-countries-list
	Parameters:	player		player object
			player-id	player ID of the player 
					(optional; defaults to the player's ID)

	Returns:	A list of the countries owned by a player.

player-countries-on-continent
	Parameters:	player		player object
			continent	a continent
			player-id	player ID of a player
					(optional; defaults to the ID of player)

	Returns:	A list of countries in continent that player-id owns.

player-cards
	Parameters:	player		player object
			player-id	player ID of a player
					(optional; defaults to the ID of player)

	Returns:	An integer representing the number of cards that a player has,
			or nil, if the player does not exist.
		
conquest-player-type
	Parameters:	player		player object
			player-id	player ID of a player
					(optional; defaults to the ID of player)

	Returns:	A symbol representing the object type of player-id (e.g. basic-player).

player-owns-country-p
	Parameters:	player		player object
			country	a country
			player-id	player ID of a player
					(optional; defaults to player's ID)

	Returns:	T, if country is owned by player-id.
			nil, otherwise.

4.2.4  Validation Methods

valid-select-country-move-p
	Parameters:	player		player object
			country	a country

	Returns:	T, if country is a valid country which is not owned;
			nil, otherwise.

valid-place-armies-move-p
	Parameters:	player		player object
			armies		an integer, the number of armies to place
			from		country that the armies are moving from
					(this should be the same as to if armies aren't moved,
					different than to if fortifying armies)
			to		country that the armies are moving to

	Returns:	T, if the specified placement of armies is a valid move;
			nil   otherwise.

valid-attack-move-p
	Parameters:	player		player object
			attacker	a country which may attack
			defender	a country which may be attacked

	Returns:	T  if the specified attack is a valid move;
			nil, otherwise.

4.2.5  Miscellaneous Methods

card-value
	Parameters:	player		player object

	Returns:	An integer representing the current number of bonus armies given
			when cards are cashed in.

country-army-capacity
	Parameters:	player		player object
		
	Returns:	An integer representing the maximum number of armies that can be
			placed on a country.

armies-given-next-turn 
	Parameters:	player		player object
			player-id	player ID of a player
					(optional; defaults to the ID of player)

	Returns:	An integer representing the number of armies that player-id would
			receive next turn if the current configuration of the board remains
			constant.

find-clump
	Parameters:	player		player object
			country	a country

	Returns:	A list containing country and all contiguous countries (recursively)
			which have the same owner.

player-clumps
	Parameters:	player		player object
			player-id	player ID of a player
					(optional; defaults to the ID of player)

	Returns:	A list of disjoint clumps which player-id owns.

find-min-paths
	Parameters:	player		player object
			from-country	a country
			to-countries	list of countries
			avoid-players	list of player-ids
					(optional; defaults to a list containing the ID of player)

	Returns:	A list of the form:  ((<cost1> <path1>) (<cost2> <path2>) ... )
			Where: 
			<costi> is an integer representing the total number of 
				armies on on the countries of <pathi>
			<pathi> is a list of countries forming the minimum path (in terms of armies)
				of the form:  (<country1> <country2> ... <countryn>)
				<country1> is a country adjacent to from-country
				<countryn> is a member of to-countries	
				none of <countryi> is owned by a member of avoid-players

4.3  User Defined Computer Player Methods

4.3.1  Select Country

Input Parameters:
	Player		The player object.

Return Value:		<country>

			That is, an available country that is selected to be owned by the player.

Control calls this method during the first round of the game.  This method should decide which of the available countries that the player wants and return the country as the value of the method.

If this method returns bogus information, the control object will just ignore it and call this method again.

Information on the available countries, enemy countries, etc. are obtained by calling one or more of the Conquest primitives.

4.3.2  Place Armies

Input Parameters:
	Player		The player object.
	turn		The number of times that this method was called previously by control
			during the player’s current turn (i.e. turn=0 the first time this method is
			called during each turn).
	n-armies	The number of armies to place.

Return Value:		(<country> <armies>)

			That is, a list containing a country and an integer  number of armies to place 
			on that country.

Control calls this method whenever armies need to be placed (i.e. Place Armies round, beginning of Attack round turns,).  The number of armies remaining to place is passed in as a parameter.  The purpose of this method is not to place all of the armies (although, it can...).  Instead, this method should specify some number of armies, n, and a country to place the n armies (for n<= n-armies).

If the placement is valid, the number of armies is subtracted from the total armies to place.  This method is called repeatedly by control until all armies have been placed.

If this method returns bogus information, the control object will just ignore it and call this method again.

Information on the player's countries, the enemy's countries, etc. are obtained by calling one or more of the Conquest primitives.

4.3.3  Attack

Input Parameters:
	Player		The player object.
	turn		The number of times that this method was called previously by control
			during the player’s current turn (i.e. turn=0 the first time this method is
			called during each turn).

Return Value:		(<attacker country> <defender country>)  OR  ‘fortify

			That is, a list consisting of a country that is owned by the player and
			a country that is not owned by the player; or the symbol fortify 

Control calls this method in the attack round of turns once the player has placed all his/her the armies.  This method should determine a single attack between a player's country and an adjacent enemy country.  

This method is called repeatedly by control  (i.e. multiple attacks within a turn) until this method tells control that it is done.  It does this by returning ‘fortify  when it is done attacking and wants to enter the fortify round.

If this method returns bogus information, the control object will just ignore it and call this method again.

Information on the player's countries, the enemy's countries, etc. are obtained by calling one or more of the Conquest primitives.

4.3.4  Fortify

Input Parameters:
	Player		The player object.
	turn		The number of times that this method was called previously by control
			during the player’s current turn (i.e. turn=0 the first time this method is
			called during each turn).

Return Value:		(<from country> <to country> <armies>)  OR  'done

			That is, a list containing a country to move armies from, a country
			to move armies to, and a number of armies to move; or the symbol done

Control calls this method in the fortify stage of a player's turn in the attack round of the game.  This method should determine a single fortify move between a player's countries (i.e. move n armies from country x to country y).

This method is called repeatedly by control (i.e. multiple fortifies within a turn) until this method tells control that it is done.  It does this by returning 'done when it wants to end the turn. 

If this method returns bogus information, the control object will just ignore it and call this method again.

Information on the player's countries, the enemy's countries, etc. are obtained by calling one or more of the Conquest primitives.

5 LISP/CLOS Programming Tips

1)  Do not use global variables.

Apart from being bad style, you will get into trouble using global variables in this program.  This version of Conquest is capable of running multiple games simultaneously.  If global variables are used to store information about a particular game, things will get screwed up when multiple games are run at the same time.  Furthermore, if a game uses multiple instantiations of your player, global variable storage will get screwed up.

To store intermediate information about a game (i.e. information that you need to save in between calls of your methods) you should define additional object variables for your player class.  An object variable is a storage place within each instantiation of a player.  The following is declaration and use of two object variables, objvar1 and objvar2:

(defclass ppm1-player (basic-player)
  ((objvar1 :initarg :objvar1 :accessor objvar1)
   (objvar2 :initarg :objvar2 :accessor objvar2))

  (:default-initargs
	:objvar1 nil	; initially, objvar1 = nil
	:objvar2 10		; initially, objvar2 = 10
))

(objvar1 player)	; this, inside of a method, accesses the objvar1
			; object variable

(setf (objvar2 player) 5)	; this, inside of a method, sets the
					; objvar2 object variable to 5

2)  Don't overuse recursion

In most cases, a loop is preferable to recursion.  Loop constructs in LISP include "dolist", "dotimes", "do", "do*", and "mapcar".  See me if you need help using LISP loops.

3)  Use high level data types

LISP, unlike scheme, provides many built in high level data types.  High level data types include structures, arrays, and hash tables.  Using these data types instead of simple lists can make your code much easier to write and debug as well as fast. 

4)  If the game freezes up...

The game will appear to freeze up if a player’s methods continuously return invalid moves.  This is because control calls player methods repeatedly until the player methods return a valid move.  If this happens, press Command-, to break execution; trace the appropriate player methods; and press Command-/ to resume the game.

6 Conquest Game Strategy Tips

The following is a partial list of Conquest strategies that I use in playing the game.  Note that some of the strategies actually conflict with each other.  A well balanced, intelligent player should determine compromises between the following strategies as well as exceptions.

1)  Defend borders

Since enemies can only attack from adjacent countries, it makes little sense to keep armies on interior countries.  In general, it is best to keep armies on border countries.  An enemy must "break through" the border countries to get to the interior countries.

A possible exception to this rule is continent borders.  Even though a continent border may not have an adjacent enemy, it is sometimes a good idea to place armies there anyway.  If an enemy breaks through a player's defenses somewhere else, the enemy will have a harder time penetrating the continent borders.

2)  Minimize borders

If the number of borders of a clump is small, a player can more effectively defend the clump (i.e. because the player can put more armies on each border).

Countries that have a fewer number of adjacent countries should also be favored as border countries of a clump since the number of possible adjacent enemies is small.

This minimization strategy usually results in the player maintaining only one clump.  That is, all of the countries owned by a player are adjacent to at least one other country owned by the player.  This generally makes the clump easier to defend.

3)  Maximize number of countries owned

The more countries that a player owns, the more extra armies that the player is given each turn.  Many times, it is advantageous to just take over weak neighboring countries that no one is interested in.  However, it is dangerous to spread out too much if a player cannot defend all of his/her countries...

4)  Maximize number of continents owned

The more continents that a player owns, the more extra armies that the player is given each turn.  It is much better to own a continent of size n than to own n countries that do not correspond to a continent.

5)  Choose continents with a high country/border ratio

Owning a large continent with a few borders is much better than owning a small continent with many borders.  The large continent is easier to defend (fewer borders) and the player receives more armies/turn due to the size of the continent.

6)  Minimize number of continents that an enemy owns

Obviously, a player should consider how an enemy is progressing.  If an enemy owns a continent, the enemy will get extra armies each turn.  If a player takes over at least one country in the enemy's continent, then the enemy is deprived of the extra armies.

7)  Take over at least one enemy country each turn

Doing this gives the player a card every turn.  This means that every four turns, the player will cash in cards and get extra armies.  When the Conquest value gets high (i.e. later in the game) this is especially important.

8)  Avoid letting an enemy defeat any of your countries

This is obvious.  As stated with 7, if the enemy takes over one of your countries each turn, the enemy will get a card each turn and will become strong.

For this reason, it is usually not a good idea to spread out too much.

9)  Completely take over a weak enemy with a large number of cards

If a player does this, the player gets the cards that the enemy owns as well as taking out one of the enemies.  At the beginning of the next turn, the player will probably get extra armies by cashing in the newly acquired cards.

10)  The enemy of your strongest enemy is your ally

If a player has an enemy that is much stronger than all of the other players, it is sometimes best not to take over the other weak players.  Chances are, the other weak players will fight against the strong enemy each turn, making it weaker.